﻿using System;
using System.Collections.Generic;

namespace NumberToWords
{
    /// <summary>
    /// Trie-like data structure used in generating possible string matches for numeric strings.
    /// </summary>
    public class NumberTrie
    {
        /// <summary>
        /// Helper class representing a node in the tree.
        /// </summary>
        private class Node
        {
            private static string NUMBER_CHARACTERS = "23456789";
            private List<string> value = new List<string>();
            private Dictionary<char, Node> children = new Dictionary<char, Node>();
            private NumberToLetterConverter converter;

            /// <summary>
            /// Create a new node that will use the given converter.
            /// </summary>
            /// <param name="converter">configuration for which letters map to which numbers</param>
            public Node(NumberToLetterConverter converter)
            {
                this.converter = converter;
            }

            public bool IsNumber(char c)
            {
                return NUMBER_CHARACTERS.LastIndexOf(c) > -1;
            }

            public bool HasChild(char c)
            {
                return this.children.ContainsKey(c);
            }

            public Node GetChild(char c)
            {
                return this.children[c];
            }

            public bool HasValues()
            {
                return this.value.Count > 0;
            }

            private void AddNext(string s, char nextCharacter, int i)
            {
                if (!this.HasChild(nextCharacter))
                {
                    this.children[nextCharacter] = new Node(this.converter);
                }
                this.GetChild(nextCharacter).Add(s, i + 1);
            }

            public void Add(string s, int i)
            {
                if (i == s.Length)
                {
                    this.value.Add(s);
                }
                if (i < s.Length)
                {
                    char nextCharacter = s[i];
                    char numberCharacter = this.converter.GetNumberForLetter(nextCharacter)[0];
                    this.AddNext(s, numberCharacter, i);
                }
            }

            public IEnumerable<string> FindMatches(string s, int i)
            {
                if (s.Length > 0)
                {
                    if (this.HasValues() && i >= s.Length)
                    {
                        foreach (string value in this.value)
                        {
                            yield return value;
                        }
                    }
                    if (i < s.Length && this.HasChild(s[i]))
                    {
                        Node nextNode = this.GetChild(s[i]);
                        foreach (string match in nextNode.FindMatches(s, i + 1))
                        {
                            yield return match;
                        }
                    }
                }
            }

            public IEnumerable<string> FindPrefixMatches(string s, int i)
            {
                if (s.Length > 0)
                {
                    if (this.HasValues() && i >= s.Length)
                    {
                        foreach (string value in this.value)
                        {
                            yield return value;
                        }
                    }
                    if (i < s.Length && this.HasChild(s[i]))
                    {
                        Node nextNode = this.GetChild(s[i]);
                        foreach (string match in nextNode.FindPrefixMatches(s, i + 1))
                        {
                            yield return match;
                        }
                    }
                    else if (i >= s.Length)
                    {
                        foreach (char key in this.children.Keys)
                        {
                            if (!IsNumber(key))
                            {
                                Node nextNode = this.children[key];
                                foreach (string match in nextNode.FindPrefixMatches(s, i + 1))
                                {
                                    yield return match;
                                }
                            }
                        }
                    }
                }
            }
        }

        private Node root = null;
        private NumberToLetterConverter converter = null;

        public NumberTrie(NumberToLetterConverter converter)
        {
            this.converter = converter;
            this.root = new Node(this.converter);
        }

        public void Add(string s)
        {
            this.root.Add(s.ToUpper(), 0);
        }

        public IEnumerable<string> FindMatches(string s)
        {
            return this.root.FindMatches(s.ToUpper(), 0);
        }

        public IEnumerable<string> FindPrefixMatches(string s)
        {
            return this.root.FindPrefixMatches(s.ToUpper(), 0);
        }
    }
}